The coding of integers finds application in many fields of computing systems. Integer coding occurs, for example, in finite field arithmetic. Finite field arithmetic has many uses in computing systems. Finite field arithmetic refers to computations based on a finite field of elements, commonly used for factoring polynomials. Galois Field mathematics is finite field mathematics, and a Galois Field has a finite number of elements, where any power of any element of the field is also an element of the field. An example of the use of finite field mathematics is in the area of cryptography, where data is encrypted for security. The coding and decoding of the data may be based on finite field mathematics, where the codes are determined from the field. Cryptography systems may use a base 2N (such as the familiar AES (Advanced Encryption Standard) algorithm) or non-2N base, where the use of non-2N bases is becoming more common.
Additionally, the storage and transmission of digital data is ubiquitous in computing systems. Receiving a transmission or retrieving stored information may reveal an error in the data, which may be caused by the storage, the transmission, and or the reading. Error correction techniques may be employed to obtain the desired data even in the presence of errors. A common error correction technique includes the use of parity bits or error codes that can help reconstruct data that has errors. Among error correction techniques are techniques implemented in accordance with or based on familiar Reed-Solomon coding.
The implementation of Reed-Solomon coders is based on the application of Galois Field mathematics. Briefly, code symbols in the Reed-Solomon coders are defined in a Galois Field of numbers represented as GF(Q), where Q is a positive integer. Relatively recent advances showed the benefits of using prime numbers as the base for the Galois Fields, rather than a 2N base. Common Reed-Solomon implementations use GF(257) and GF(65,537), which are prime numbers that are also 28+1 and 216+1, respectively. These prime bases also have application in the use of cryptography systems. These prime bases have the property of being a single number higher than what can be represented by an 8-bit or a 16-bit representation, respectively, where B- and 16-bits are useful for binary computing systems.
However, where the base field is GF(257) or GF(65,537), certain codes cannot be represented reliably using 8 or 16 bits, since there is one more element than either representation can hold. The extension of that problem is also seen in other fields having a non-2N base. Typically, this problem is resolved by either ignoring the problem (which generally cannot be done for values other than 257 or 65,537), using a complex conversion process, which requires additional logic and processing, or using the additional bit to represent the codes, which increases data use in the storage and/or transmission bandwidth. Thus, these known resolutions are typically limited to the use of primes of the form 2N+1, because other primes exacerbate the problem. The primary issue is that for values not of the form 2N (with the problem ignored) or 2N+1 is that more bits than necessary are used for the codes. Consider a base 53. GF(53) includes the values 0-52, which would likely be represented with 6-bit encoding, because any value 0-63 could be represented with 6 bits. Thus, current coding schemes are often inefficient.